W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bitocja i Bajtocja planują podpisać rozejm po długotrwałej wojnie. Państwa te muszą zdecydować, do kogo będą należeć poszczególne miasta. Władcy Bitocji i Bajtocji postanowili, że dokonają podziału tak, aby zminimalizować liczbę bezpośrednich połączeń między parami miast, należącymi do różnych państw.
Twoim zadaniem jest podanie wspomnianej wyżej liczby po podpisaniu rozejmu.
Pierwszy wiersz wejścia zawiera dwie liczby całkowite i (), oznaczające odpowiednio liczbę miast oraz liczbę połączeń. Drugi wiersz wejścia zawiera ciąg liczb całkowitych (). Jeżeli ma wartość 1, to miasto należeć będzie do Bitocji, 2, to miasto należeć będzie do Bajtocji, 3, to miasto należy przydzielić albo do Bajtocji albo do Bitocji. Kolejnych wierszy zawiera opisy połączeń między miastami. Każdy wiersz opisu zawierać będzie dwie liczby , , () oznaczające, że miasta i są połączone bezpośrednią drogą. Żadna para (, ) się nie powtórzy.
Możesz założyć, że w testach wartych około punktów zachodzi dodatkowy warunek
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie połączeń między miastami należącymi do Bitocji i Bajtocji po podpisaniu rozejmu.
Dla danych wejściowych:
4 4 1 1 3 2 1 2 1 3 2 3 3 4
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu: Jeżeli miasto numer 3 zostanie przydzielone Bitocji, to występować będzie tylko jedno połączenie między miastami Bitocji i Bajtocji - między miastami 3 i 4.
Autor zadania: Joanna Bujnowska (zapożyczenie).